//题目:
// 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
// (1) 每次只能移动一个盘子;
// (2) 盘子只能从柱子顶端滑出移到下一根柱子;
// (3) 盘子只能叠在比它大的盘子上。
// 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
// 你需要原地修改栈。
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    void bfs(vector<int>& x,vector<int>& y,vector<int>& z,int n)
    {
        //出口
        if(n==1)
        {
            //直接把A最上面的盘子转移到C最上面
            z.push_back(x[x.size()-1]);
            x.pop_back();
            return;
        }
        //①先将A上面N-1个盘子借助C全部转移到B上 
        bfs(x,z,y,n-1);

        //②再将A最上面的盘子直接转移到C上
        z.push_back(x[x.size()-1]);
        x.pop_back();

        //③最后将B上的N-1个盘子借助A全部转移到C上
        bfs(y,x,z,n-1);
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        //主问题:将柱子A上的N个盘子借助柱子B，全部转移到柱子C上
        //子问题:①先将A上面N-1个盘子借助C全部转移到B上  
        //      ②再将A最下面的盘子直接转移到C上
        //      ③最后将B上的N-1个盘子借助A全部转移到C上
        if(A.size()>0)
            bfs(A,B,C,A.size());
    }
};